package org.lql.algo.codecrush.hot100.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-08-31 11:14
 * @description: 78. 子集 <a href="https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class Subsets {

	int n;
	List<Integer> chosen = new ArrayList<Integer>();
	List<List<Integer>> ans = new ArrayList<List<Integer>>();

	public List<List<Integer>> subsets(int[] nums) {
		n = nums.length;
		recur(nums, 0);
		return ans;
	}

	public void recur(int[] nums, int pos) {
		if (pos == n) {
			ans.add(new ArrayList<>(chosen));
			return;
		}
		// 每层相似逻辑：nums[i]选或不选
		// 1、不选择元素往下一个分支走
		recur(nums, pos + 1);
		// 2、选择元素往下一个分支走，结束之后需要还原选择的内容
		chosen.add(nums[pos]);
		recur(nums, pos + 1);
		chosen.remove(chosen.size() - 1);
	}

	public static void main(String[] args) {
		Subsets subsets = new Subsets();
		System.out.println(subsets.subsets(new int[]{1, 2, 3}));
	}
}
